//给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 高度平衡 二叉搜索树。 
//
// 高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。 
//
// 
//
// 示例 1： 
//
// 
//输入：nums = [-10,-3,0,5,9]
//输出：[0,-3,9,-10,null,5]
//解释：[0,-10,5,null,-3,null,9] 也将被视为正确答案：
//
// 
//
// 示例 2： 
//
// 
//输入：nums = [1,3]
//输出：[3,1]
//解释：[1,null,3] 和 [3,1] 都是高度平衡二叉搜索树。
// 
//
// 
//
// 提示： 
//
// 
// 1 <= nums.length <= 10⁴ 
// -10⁴ <= nums[i] <= 10⁴ 
// nums 按 严格递增 顺序排列 
// 
// Related Topics 树 二叉搜索树 数组 分治 二叉树 👍 1004 👎 0

package leetcode.editor.cn;

import java.util.LinkedList;
import java.util.Queue;

class ConvertSortedArrayToBinarySearchTree {
    public static void main(String[] args) {
        Solution solution = new ConvertSortedArrayToBinarySearchTree().new Solution();
        solution.sortedArrayToBST(new int[]{-10, -3, 0, 5, 9});
    }
    //leetcode submit region begin(Prohibit modification and deletion)

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    class Solution {
        /**
         * 递归法（左闭右开）
         *
         * @param nums
         * @return
         */
        /*public TreeNode sortedArrayToBST(int[] nums) {
            if (nums.length == 0) {
                return null;
            }
            return traversal(nums, 0, nums.length);
        }

        public TreeNode traversal(int[] num, int left, int right) {
            if ((right - left) < 1) {   // 如果数组大小为零的话，说明是空节点了。
                return null;
            }

            // 找到中间元素，从中间开始才不会高度差超过一
            int mid = (left + right) / 2;
            TreeNode root = new TreeNode(num[mid]);

            // 采用的是左闭右开的区间划分
            root.left = traversal(num, left, mid);
            root.right = traversal(num, mid + 1, right);

            return root;
        }*/


        /**
         * 迭代法（左闭右闭）
         *
         * @param nums
         * @return
         */
        public TreeNode sortedArrayToBST(int[] nums) {
            if (nums.length == 0) return null;

            TreeNode root = new TreeNode(0);
            Queue<TreeNode> nodeQueue = new LinkedList<>(); // 保存遍历的节点
            Queue<Integer> leftQueue = new LinkedList<>();  // 保存遍历的左边界
            Queue<Integer> rightQueue = new LinkedList<>(); // 保存遍历的右边界

            nodeQueue.offer(root);  // 先将根节点入队，才能将节点连成整棵树
            leftQueue.offer(0);  // 初始化左边界
            rightQueue.offer(nums.length - 1);  // 初始化右边界

            while (!nodeQueue.isEmpty()) {
                TreeNode curNode = nodeQueue.poll();
                Integer left = leftQueue.poll();
                Integer right = rightQueue.poll();
                int mid = (left + right) / 2;
//                int mid = left + (right - left) / 2;

                curNode.val = nums[mid];    // 将mid对应的元素给中间节点

                if (left <= mid - 1) {   // 处理左节点
                    curNode.left = new TreeNode(0); // 生成左节点并入队
                    nodeQueue.offer(curNode.left);
                    leftQueue.offer(left);  // 作弊右开处理
                    rightQueue.offer(mid - 1);
                }

                if (right >= mid + 1) {   // 处理右节点
                    curNode.right = new TreeNode(0); // 生成左节点并入队
                    nodeQueue.offer(curNode.right);
                    leftQueue.offer(mid + 1);  // 作弊右开处理
                    rightQueue.offer(right);
                }
            }

            return root;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
